package com.fulu.javabase.arithmetic.array;

/**
 * Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
 * You must write an algorithm with O(log n) runtime complexity.
 * https://leetcode.cn/problems/binary-search/
 */
public class BinarySearch {
    public int search(int[] nums, int target) {
        int length = nums.length;
        if(length == 0) return -1;

        int start = 0;
        int end = length - 1;
        while(true){
            if(end == start){
                if(nums[end] == target) return end;
                else return -1;
            }
            int i = (end - start) / 2 + start;
            if(nums[i] == target) return i;
            if(nums[i] > target) {
                end = i == start ? start : i - 1;
            }else{
                start = i == end ? end : i + 1;
            }
        }
    }
    public int search1(int[] nums, int target) {
        int length = nums.length;
        if(length == 0) return -1;

        int start = 0;
        int end = length - 1;
        while(start <= end){
            int middle = start + (end - start) / 2;
            if(nums[middle] == target){
                return middle;
            }else if(nums[middle] > target){
                end = middle - 1;
            }else{
                start = start + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,3,5,9,12, 13};
        int target = 9;
        BinarySearch binarySearch = new BinarySearch();
        long begin = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            binarySearch.search(nums, target);
        }
//        System.out.println(result);
        long end = System.currentTimeMillis();
        System.out.println(end - begin);
        // 16ms
    }
}
